package com.shixianjun.sort;

public class _4_希尔排序 implements Sortable {

    @Override
    public void sort(SortableElement[] arr) {
        /**
         * h = 1
         * h = 3 * h + 1
         * */
        int gap = 1;
        int i;
        int j;
        SortableElement tem;
        while (gap <= arr.length / 3) {
            gap = 3 * gap + 1;
        }

        for (; gap >= 1; gap = (gap - 1) / 3) {
            for (i = gap; i < arr.length; i++) {
                tem = arr[i];
                for (j = i; j >= gap && arr[j - gap].value > tem.value; j-= gap) {
                    arr[j] = arr[j - gap];
                }
                arr[j] = tem;
            }
        }
    }
}
